1. Field
The present disclosure relates to computer systems and methods in which data resources are shared among data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the disclosure concerns an implementation of a mutual exclusion mechanism known as “read-copy update” in a computing environment wherein the data consumers are subject to being preempted while referencing shared data.
2. Description of the Prior Art
By way of background, read-copy update (also known as “RCU”) is a mutual exclusion technique that permits shared data to be accessed for reading without the use of locks, writes to shared memory, memory barriers, atomic instructions, or other computationally expensive synchronization mechanisms, while still permitting the data to be updated (modify, delete, insert, etc.) concurrently. The technique is well suited to both uniprocessor and multiprocessor computing environments wherein the number of read operations (readers) accessing a shared data set is large in comparison to the number of update operations (updaters), and wherein the overhead cost of employing other mutual exclusion techniques (such as locks) for each read operation would be high. By way of example, a network routing table that is updated at most once every few minutes but searched many thousands of times per second is a case where read-side lock acquisition would be quite burdensome.
The read-copy update technique implements data updates in two phases. In the first (initial update) phase, the actual data update is carried out in a manner that temporarily preserves two views of the data being updated. One view is the old (pre-update) data state that is maintained for the benefit of read operations that may have been referencing the data concurrently with the update. The other view is the new (post-update) data state that is seen by operations that access the data following the update. In the second (deferred update) phase, the old data state is removed following a “grace period” that is long enough to ensure that the first group of read operations will no longer maintain references to the pre-update data. The second-phase update operation typically comprises freeing a stale data element to reclaim its memory. In certain RCU implementations, the second-phase update operation may comprise something else, such as changing an operational state according to the first-phase update.
FIGS. 1A-1D illustrate the use of read-copy update to modify a data element B in a group of data elements A, B and C. The data elements A, B, and C are arranged in a singly-linked list that is traversed in acyclic fashion, with each element containing a pointer to a next element in the list (or a NULL pointer for the last element) in addition to storing some item of data. A global pointer (not shown) is assumed to point to data element A, the first member of the list. Persons skilled in the art will appreciate that the data elements A, B and C can be implemented using any of a variety of conventional programming constructs, including but not limited to, data structures defined by C-language “struct” variables. Moreover, the list itself is a type of data structure.
It is assumed that the data element list of FIGS. 1A-1D is traversed (without locking) by multiple readers and occasionally updated by updaters that delete, insert or modify data elements in the list. In FIG. 1A, the data element B is being referenced by a reader r1, as shown by the vertical arrow below the data element. In FIG. 1B, an updater u1 wishes to update the linked list by modifying data element B. Instead of simply updating this data element without regard to the fact that r1 is referencing it (which might crash r1), u1 preserves B while generating an updated version thereof (shown in FIG. 1C as data element B′) and inserting it into the linked list. This is done by u1 acquiring an appropriate lock (to exclude other updaters), allocating new memory for B′, copying the contents of B to B′, modifying B′ as needed, updating the pointer from A to B so that it points to B′, and releasing the lock. In current versions of the Linux® kernel, pointer updates performed by updaters can be implemented using the rcu_assign_pointer( ) primitive. As an alternative to locking during the update operation, other techniques such as non-blocking synchronization or a designated update thread could be used to serialize data updates. All subsequent (post update) readers that traverse the linked list, such as the reader r2, will see the effect of the update operation by encountering B′ as they dereference B's pointer. On the other hand, the old reader r1 will be unaffected because the original version of B and its pointer to C are retained. Although r1 will now be reading stale data, there are many cases where this can be tolerated, such as when data elements track the state of components external to the computer system (e.g., network connectivity) and must tolerate old data because of communication delays. In current versions of the Linux® kernel, pointer dereferences performed by readers can be implemented using the rcu_dereference( ) primitive.
At some subsequent time following the update, r1 will have continued its traversal of the linked list and moved its reference off of B. In addition, there will be a time at which no other reader process is entitled to access B. It is at this point, representing an expiration of the grace period referred to above, that u1 can free B, as shown in FIG. 1D.
FIGS. 2A-2C illustrate the use of read-copy update to delete a data element B in a singly-linked list of data elements A, B and C. As shown in FIG. 2A, a reader r1 is assumed be currently referencing B and an updater u1 wishes to delete B. As shown in FIG. 2B, the updater u1 updates the pointer from A to B so that A now points to C. In this way, r1 is not disturbed but a subsequent reader r2 sees the effect of the deletion. As shown in FIG. 2C, r1 will subsequently move its reference off of B, allowing B to be freed following the expiration of a grace period.
In the context of the read-copy update mechanism, a grace period represents the point at which all running tasks (e.g., processes, threads or other work) having access to a data element guarded by read-copy update have passed through a “quiescent state” in which they can no longer maintain references to the data element, assert locks thereon, or make any assumptions about data element state. By convention, for operating system kernel code paths, a context switch, an idle loop, and user mode execution all represent quiescent states for any given CPU running non-preemptible code (as can other operations that will not be listed here). The reason for this is that a non-preemptible kernel will always complete a particular operation (e.g., servicing a system call while running in process context) prior to a context switch.
In FIG. 3, four tasks 0, 1, 2, and 3 running on four separate CPUs are shown to pass periodically through quiescent states (represented by the double vertical bars). The grace period (shown by the dotted vertical lines) encompasses the time frame in which all four tasks that began before the start of the grace period have passed through one quiescent state. If the four tasks 0, 1, 2, and 3 were reader tasks traversing the linked lists of FIGS. 1A-1D or FIGS. 2A-2C, none of these tasks having reference to the old data element B prior to the grace period could maintain a reference thereto following the grace period. All post grace period searches conducted by these tasks would bypass B by following the updated pointers created by the updater.
Grace periods may synchronous or asynchronous. According to the synchronous technique, an updater performs the first phase update operation, blocks (waits) until a grace period has completed, and then implements the second phase update operation, such as by removing stale data. According to the asynchronous technique, an updater performs the first phase update operation, specifies the second phase update operation as a callback, then resumes other processing with the knowledge that the callback will eventually be processed at the end of a grace period. Advantageously, callbacks requested by one or more updaters can be batched (e.g., on callback lists) and processed as a group at the end of an asynchronous grace period. This allows asynchronous grace period overhead to be amortized over plural deferred update operations. In some RCU implementations, asynchronous grace period processing is the norm but a synchronous expedited grace period, sometimes referred to as a “Big Hammer” grace period, is also available for updaters that need it. This expedited grace period forces a context switch (and thus a quiescent state) on each processor so that an updater can quickly perform its second-phase update operation. Existing callbacks associated with asynchronous grace periods are not affected. They must await the end of an asynchronous grace period before becoming ripe for processing.
It will be appreciated from the foregoing discussion that the fundamental operation of the RCU synchronization technique entails waiting for all readers associated with a particular grace period to complete. Multiprocessor implementations of RCU must observe or influence the actions performed by multiple processors, whereas uniprocessor implementations do not. In so-called “non-preemptible” variants of RCU, readers are never preempted and rescheduled within an RCU read-side critical section. Orderly grace period processing in such implementations may then be ensured by either forcing or waiting for each reader's processor to pass through a quiescent state.
The situation is different for so-called “preemptible” variants of RCU wherein readers are subject to preemption within RCU read-side critical sections. In that case, a context switch will occur but will not constitute a quiescent state as in the case of non-preemptible RCU. For example, in a preemptible operating system kernel, the servicing of a system call during process context could be interrupted by a higher priority task while the system call code is in the midst of an RCU read-side critical section. In this situation, other techniques are required to track quiescent states. The approach most often used is to treat all reader processing outside of an RCU read-side critical section as a quiescent state, and to provide some form of tracking methodology that allows readers to specify when they are performing RCU read-side critical section processing. A grace period will not end until all readers being tracked in this manner indicate that they have completed such processing. Throughout the present document, readers that are preempted within an RCU read-side critical section will also be referred to as “blocked” readers.
Unfortunately, separate tracking of preempted readers is typically required for asynchronous grace periods and synchronous expedited grace periods because there is not necessarily any direct relation between the two. They might overlap, be disjoint, or have one wholly contained within the other. This separate tracking complicates RCU grace period detection processing. Preemptible readers may also be tracked in order to determine which readers are tardy in completing their RCU read-side critical section processing and thus may be blocked by a higher priority process. Such preempted readers can be given a scheduling priority boost in RCU implementations that support such functionality. Without a priority boost, such readers could delay the end of a current grace period, potentially leading to problems such as an out-of-memory (OOM) condition caused by excessive callback accumulation. Unfortunately, tracking preemptible readers for possible priority boosting further complicates RCU grace period detection processing.
In conventional RCU implementations, the tracking of preemptible readers has been accomplished using a number of methods. According to one such technique, per-processor counters track the number of still-in-progress RCU read-side critical sections that began on the corresponding processors (see P. McKenney et al., “Extending RCU for Realtime and Embedded Workloads”, Aug. 11, 2006). According to a variant of this technique, per-processor counters track the difference between the number of RCU read-side critical sections that began on a given processor and the number of RCU read-side critical sections that ended on that same processor (see Id.; P. McKenney, “The Design of Preemptible Read-Copy Update”, Aug. 7, 2007). Both of the foregoing techniques have several shortcomings, to with: (1) expensive atomic operations and memory barriers are required in RCU read-side primitives; (2) there is no convenient way to determine which tasks block an expedited grace period, and (3) there is no convenient way to determine which tasks need priority boosting in order to permit the current grace period to end.
One existing RCU implementation augments the above counter-based techniques with a set of lists linking together tasks that blocked while in an RCU read-side critical section during a given time period. Tasks that block and then remain in the RCU read-side critical section for too long are priority boosted (see P. McKenney, “Priority-Boosting RCU Read-Side Critical Sections”, Apr. 16, 2007). This technique also has shortcomings, namely: (1) because there is no direct connection between grace periods and time periods, this approach can boost tasks that do not need to be boosted (unnecessarily delaying execution of real-time tasks), and also can unnecessarily delay boosting tasks that do need to be boosted, (2) there is no convenient way to determine which tasks block an expedited grace period, and (3) the array of lists consumes considerable memory, which can be a problem on embedded platforms.
According to a further existing RCU implementation, any task that is preempted while in an RCU read-side critical section is given an immediate priority boost (see S. Rostedt, “[RFC PATCH] RFC Preemption Priority Boosting”, Oct. 3, 2007). A disadvantage of this approach is that tasks may be priority boosted that do not need it, thereby unnecessarily delaying execution of real-time tasks.
A still further existing RCU implementation, known as hierarchical RCU, maintains an array [ ] of four blocked reader lists. The first list tracks readers that block neither the current synchronous nor the current asynchronous grace periods, the second list tracks readers that block the current synchronous grace period but not the current asynchronous grace period, the third list tracks readers that do not block the current synchronous grace period but do block the current asynchronous grace period, and the fourth list tracks readers that block both the current synchronous and the current asynchronous grace periods (see I. Molnar et al. “Linux/kernel/rcutree.h”, 2008, lines 120-124 (“struct list_head blocked_tasks[4]” field of “struct rcu_node” data structure). A disadvantage of this approach is that four separate lists must be managed. Also, there are no lists tracking boosted readers. However, commonly owned U.S. Patent Application Publication No. 2011/0055183 discloses that two boost lists (respectively indexed to the current and previous asynchronous grace periods) may be used in conjunction with blocked reader tracking. However, combining boost list tracking with the four-list blocked reader tracking system of Hierarchical RCU, would double the existing four lists to a total of eight lists. This is because each of the existing four lists would have a boost list counterpart to identify blocked readers that have been boosted.